Social networks can be represented as graphs with a node for each user's account and an edge between nodes representing communications between user accounts, or relationships in the social network such as “friends” or “following.” The underlying social structures of such graphs can be used to optimize a variety of applications such as search engines and advertising delivery systems. For example, users of the social network can be provided advertisements for products that their friends in the social network have purchased.
While social network graphs are useful, there are difficulties associated with their use. First, while users who are associated in the social network are often similar, some users with relationships in the social network may be sufficiently different to appear random. Second, social networks are multiplex in that they may be a union of multiple independent relationships among the users. For example, users may interact with users in the social network that they work with, go to school with, or are related to, which may result in connections between users in the graph who have little in common other than a single relationship. These weakly connected users may introduce noise into the social network graph that may overstate the similarity of the users. The noise may further lead to poor performance for search engines or advertising delivery systems that rely on the social network graphs.